package com.example.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/7/30
 * 对称二叉树
 */
public class SymmetricTree {

    /**--------------这个方法想法是把树整成list，通过对比，看看是否对称------------------*/
    /**
     * 这道题通过了 195/198 不知道那里错了  以后再看吧
     */
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> list=new ArrayList<>();
        dfs(root,list);
        int right=list.size()-1;
        int left=0;
        while (left<right)
        {
            if(list.get(left).val==list.get(right).val) {
                left++;
                right--;
            }else {
                return false;
            }
        }
        return true;
    }

    private void dfs(TreeNode root, List<TreeNode> list) {
        if(root==null)
        {
            return;
        }
        dfs(root.left,list);
        list.add(root);
        dfs(root.right,list);
    }



    /**-----------对比内外侧的节点-------------*/
    public boolean isSymmetric1(TreeNode root)
    {
        return compareTreeNode(root.left,root.right);
    }

    private boolean compareTreeNode(TreeNode left,TreeNode right) {

        if(left==null&&right!=null)
        {
            return false;
        }
        if(left!=null&&right==null)
        {
            return false;
        }
        if(left==null&&right==null)
        {
            return true;
        }
        if(left.val!=right.val)
        {
            return false;
        }
        boolean compareOut=compareTreeNode(left.left,right.right);
        boolean compareIn=compareTreeNode(left.right,right.left);
        return compareOut&&compareIn;
    }
}
